package com.datastructures2.graph.无向图;

import edu.princeton.cs.algs4.Stack;


/**
 * 深度优先搜索查找图中路径
 */
public class DepthFirstPaths {
    /**
     * 标记顶点i是否被访问
     */
    private boolean[] marked;
    /**
     * 从起点到一个顶点的已知路径上的最后一个顶点
     * 如 v->w->x  则edgeTo[w]=v,edgeTo[x]=w
     */
    private int[] edgeTo;
    /**
     * 遍历的起点
     */
    private final int s;         // source vertex

    /**
     * Computes a path between {@code s} and every other vertex in graph {@code G}.
     * @param G the graph
     * @param s the source vertex
     * @throws IllegalArgumentException unless {@code 0 <= s < V}
     */
    public DepthFirstPaths(Graph G, int s) {
        this.s = s;
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        validateVertex(s);
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v]=true;
        for (int w:G.adj(v)){
            if (!marked[w]){
                edgeTo[w]=v;
                dfs(G,w);
            }
        }
    }

    /**
     * 是否存在从s到v的路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }


    /**
     * s到v的路径，如果不存在则返回null
     * @param v
     * @return
     */
    public  Iterable<Integer> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v)){
            return null;
        }
        Stack<Integer> paths=new Stack<>();
        for (int i = v; i !=s ; i=edgeTo[i]) {
            paths.push(i);
        }
        paths.push(s);
        return paths;
    }

    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }


    public static void main(String[] args) {
        Graph graph=new Graph(6);
        graph.addEdge(0,2);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(2,4);
        graph.addEdge(3,5);
        graph.addEdge(3,4);
        DepthFirstPaths dfs=new DepthFirstPaths(graph,0);
        Iterable<Integer> paths = dfs.pathTo(4);
        for (Integer i:paths){
            System.out.println(i.toString());
        }
    }


}
